Euclidean division is a basic arithmetic operation that is founded upon a property that given any two integers a (dividend) and b≠0 (divisor), there exists another pair of integers q (quotient) and r (remainder), such that a=q·b+r, where 0≦r<|b|. In computer software, q=a div b (where div is the integer division operation) and r=a mod b (where mod is the modulo or residue operation). (Note: slightly different definitions of div and mod in some computer systems and programming languages, involving rules for rounding or truncating the quotient, can affect the result when one or more negative integers are involved. But in each case, the relationship to the definitions given above is known.)
In electronic digital hardware, various methods of performing division computations are known, such as multiplication by the reciprocal b−1 of the divisor, or repeated subtraction with the divisor or with some multiple of the divisor, in order to make use of the available multiplier or adder processing circuitry. Efficient techniques for operating upon extremely large (multi-word) integers are sought.
Euclidean division also refers to a related method described in Euclid's Elements (circa 300 BCE) for finding the greatest common divisor (GCD) of a pair of integers, which involves iteration in a series of rounds of mutual division. This method has practical application today in error correcting codes (e.g., Reed-Solomon codes) and in asymmetric block ciphers (i.e., public key cryptographic systems, such as Rivest-Shamir-Adleman type cryptosystems). In the error correcting applications, the basic Euclidean division algorithm is usually extended to operate upon polynomials with integer coefficients in some finite field. This is also the case for certain ciphers based on elliptic curve sets. See U.S. Pat. Nos. 5,185,711 and 5,367,478 to Hattori, and U.S. Pat. No. 5,951,677 to Wolf et al. for implementations of Euclidean division to error correction processing. U.S. Patent Application Publication No. 2004/0158597 A1 of Ye et al. illustrates an elliptic curve cryptosystem that implements inversion of polynomials in a finite field K(n) using extended Euclidean division. For those public key ciphers based on products of large primes, the Euclidean division algorithm may be applied, for example, to invert an extremely large integer modulus, as part of deriving related sets of public and private keys.
In as much as the integers or integer coefficients involved in these iterated division calculations are typically extremely large, the overall calculation time can be improved considerably if the basic division operation of each iterated round could be performed faster. Division operations that are based on first obtaining the reciprocal of the divisor become especially time consuming as the size of the divisor increases.
Hardware implementation of cryptographic algorithms (such as in RISC-based smart cards) may be susceptible to side-channel attacks, including power analysis and timing attacks. An attacker externally monitors aspects of the hardware that are accessible, such as current through chip pads or electromagnetic emissions from a chip, in order to obtain information about internal operations which may be subjected to various analysis in an effort to uncover the encryption key. Typically, secure microcontrollers for smart cards use various kinds of hardware-based countermeasures to thwart such attacks.
While some software-level countermeasures introduced into a cryptographic algorithm itself might also be considered, it is very important that may such countermeasures not adversely affect the speed or accuracy of the underlying computations. Not all of the internal operations of a cryptographic algorithm are as readily adaptable so as to incorporate software countermeasures without appreciable slowing and without jeopardizing accuracy of final result. Arithmetic operations in particular, including Euclidean division, generally require a specific result from operating upon given operands. Any changes that would obtain an erroneous final result would clearly be unwelcome.